Search results for "finite [mass]"
showing 10 items of 356 documents
Hamming, Permutations and Automata
2007
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than superexponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We prove that there is an infinite sequence of distinct int…
Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
2008
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We use a novel proof technique based on Kolmogorov complex…
Ambainis-Freivalds’ Algorithm for Measure-Once Automata
2001
An algorithm given by Ambainis and Freivalds [1] constructs a quantum finite automaton (QFA) with O(log p) states recognizing the language Lp = {ai| i is divisible by p} with probability 1 - Ɛ , for any Ɛ > 0 and arbitrary prime p. In [4] we gave examples showing that the algorithm is applicable also to quantum automata of very limited size. However, the Ambainis-Freivalds algoritm is tailored to constructing a measure-many QFA (defined by Kondacs andWatrous [2]), which cannot be implemented on existing quantum computers. In this paper we modify the algorithm to construct a measure-once QFA of Moore and Crutchfield [3] and give examples of parameters for this automaton. We show for the lang…
Improved Constructions of Quantum Automata
2008
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use $\frac{4}{\epsilon} \log 2p + O(1)$ states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of logp than the previously known construction of [2]. Similarly to [2], our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some preliminary results in this direction.
Coding Partitions: Regularity, Maximality and Global Ambiguity
2007
The canonical coding partition of a set of words is the finest partition such that the words contained in at least two factorizations of a same sequence belong to a same class. In the case the set is not uniquely decipherable, it partitions the set into one unambiguous class and other parts that localize the ambiguities in the factorizations of finite sequences. We firstly prove that the canonical coding partition of a regular set contains a finite number of regular classes. We give an algorithm for computing this partition. We then investigate maximality conditions in a coding partition and we prove, in the regular case, the equivalence between two different notions of maximality. As an ap…
A NOTE ON THE ASYMPTOTIC PROBABILITIES OF EXISTENTIAL SECOND-ORDER MINIMAL GÖDEL SENTENCES WITH EQUALITY
1995
The minimal Gödel class is the class of first-order prenex sentences whose quantifier prefix consists of two universal quantifiers followed by just one existential quantifier. We prove that asymptotic probabilities of existential second-order sentences, whose first-order part is in the minimal Gödel class, form a dense subset of the unit interval.
Real constituents of permutation characters
2022
Abstract We prove a broad generalization of a theorem of W. Burnside about the existence of real characters of finite groups to permutation characters. If G is a finite group, under the necessary hypothesis of O 2 ′ ( G ) = G , we can also give some control on the parity of multiplicities of the constituents of permutation characters (a result that needs the Classification of Finite Simple Groups). Along the way, we give a new characterization of the 2-closed finite groups using odd-order real elements of the group. All this can be seen as a contribution to Brauer's Problem 11 which asks how much information about subgroups of a finite group can be determined by the character table.
Extensions of cocycles for hyperfinite actions and applications
1997
Given a countable, hyperfinite, ergodic and measure-preserving equivalence relationR on a standard probability space (X, ℬ, μ) and an elementW of the normalizerN (R) ofR, we investigate the problem of extendingR-cocycles to\(\bar R\), where\(\bar R\) is the relation generated byR andW. As an application, we obtain that for a Bernoulli automorphism the smallest family of natural factors in sense of [6] consists of all factors. Given an automorphism which is embeddable in a measurable flow and a compact, metric group, we show that for a typical cocycle we cannot lift the whole flow to the centralizer of the corresponding group extension.
4-Manifold topology I: Subexponential groups
1995
The technical lemma underlying the 5-dimensional topological s-cobordism conjecture and the 4-dimensional topological surgery conjecture is a purely smooth category statement about locating ~-null immersions of disks. These conjectures are theorems precisely for those fundamental groups ("good groups") where the ~l-null disk lemma (NDL) holds. We expand the class of known good groups to all groups of subexponential growth and those that can be formed from these by a finite number of application of two opera- tions: (1) extension and (2) direct limit. The finitely generated groups in this class are amenable and no amenable group is known to lie outside this class.
A Local Approach to Certain Classes of Finite Groups
2003
Abstract We develop several local approaches for the three classes of finite groups: T-groups (normality is a transitive relation) and PT-groups (permutability is a transitive relation) and PST-groups (S-permutability is a transitive relation). Here a subgroup of a finite group G is S-permutable if it permutes with all the Sylow subgroup of G.